The invention relates generally to arithmetic logic units (ALU) and more particularly to arithmetic logic units that perform multiplication and accumulate operations using multipliers having Wallace tree addition structures.
The multiplication and accumulation (MAC) operation is a common operation performed in arithmetic logic units. ALUs are typically used in microprocessors and other processing units. A conventional MAC structure may have a multiplier of 16 bits for example, and an accumulator with a much larger bit size such as 64 bits or 128 bits. Such MAC structure may use Wallace tree structures to produce the intermediate product term. An additional carry save adder is used to combine the intermediate product with the contents of the accumulator. A carry propagate add operation is used to obtain the final MAC result. MAC structures may be required to process signed and unsigned values. However, multiplying and accumulating unsigned values may require a larger multiplier structure to allow intermediate product terms to be extended to the proper accumulator size (format). This larger structure can result in larger sized multipliers resulting in higher cost dies and higher power dissipation.
In addition, MAC operations can require a saturating addition or a normal addition. A saturation condition may result when the MAC size is exceeded due to the oversize of the result. The saturation condition is determined by the carry out of the final addition. However, the addition may also produce a carry due to the extension of the intermediate product into the proper accumulator size. A distinction has to be made so that the data is not misinterpreted.
Consequently, there exists a need for a multiplier carry bit compression apparatus and method for a multiplier using Wallace tree addition structures that facilitates a reduction is multiplier size and facilitates saturating MAC operation.